<html>
  <head>
  <title>distanceCalculator.py</title>
  </head>
  <body>
  <h3>distanceCalculator.py (<a href="../distanceCalculator.py">original</a>)</h3>
  <hr>
  <pre>
<span style="color: green; font-style: italic"># distanceCalculator.py
# ---------------------
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html

</span><span style="color: darkred">"""
This file contains a Distancer object which computes and 
caches the shortest path between any two points in the maze. It 
returns a Manhattan distance between two points if the maze distance
has not yet been calculated. 

Example:
distancer = Distancer(gameState.data.layout)
distancer.getDistance( (1,1), (10,10) )

The Distancer object also serves as an example of sharing data 
safely among agents via a global dictionary (distanceMap), 
and performing asynchronous computation via threads. These
examples may help you in designing your own objects, but you
shouldn't need to modify the Distancer code in order to use its
distances.
"""

</span><span style="color: blue; font-weight: bold">import </span>threading<span style="font-weight: bold">, </span>sys<span style="font-weight: bold">, </span>time<span style="font-weight: bold">, </span>random

<span style="color: blue; font-weight: bold">class </span>Distancer<span style="font-weight: bold">:
  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>layout<span style="font-weight: bold">, </span>background<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">, </span>default<span style="font-weight: bold">=</span><span style="color: red">10000</span><span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Initialize with Distancer(layout).  Changing default is unnecessary.
    
    This will start computing maze distances in the background and use them
    as soon as they are ready.  In the meantime, it returns manhattan distance.
    
    To compute all maze distances on initialization, set background=False
    """
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_distances <span style="font-weight: bold">= </span><span style="color: blue">None
    self</span><span style="font-weight: bold">.</span>default <span style="font-weight: bold">= </span>default
    
    <span style="color: green; font-style: italic"># Start computing distances in the background; when the dc finishes,
    # it will fill in self._distances for us.
    </span>dc <span style="font-weight: bold">= </span>DistanceCalculator<span style="font-weight: bold">()
    </span>dc<span style="font-weight: bold">.</span>setAttr<span style="font-weight: bold">(</span>layout<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">)
    </span>dc<span style="font-weight: bold">.</span>setDaemon<span style="font-weight: bold">(</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>background<span style="font-weight: bold">:
      </span>dc<span style="font-weight: bold">.</span>start<span style="font-weight: bold">()
    </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
      </span>dc<span style="font-weight: bold">.</span>run<span style="font-weight: bold">()
    
  </span><span style="color: blue; font-weight: bold">def </span>getDistance<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>pos1<span style="font-weight: bold">, </span>pos2<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    The getDistance function is the only one you'll need after you create the object.
    """
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_distances <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>manhattanDistance<span style="font-weight: bold">(</span>pos1<span style="font-weight: bold">, </span>pos2<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>isInt<span style="font-weight: bold">(</span>pos1<span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span>isInt<span style="font-weight: bold">(</span>pos2<span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>getDistanceOnGrid<span style="font-weight: bold">(</span>pos1<span style="font-weight: bold">, </span>pos2<span style="font-weight: bold">)
    </span>pos1Grids <span style="font-weight: bold">= </span>getGrids2D<span style="font-weight: bold">(</span>pos1<span style="font-weight: bold">)
    </span>pos2Grids <span style="font-weight: bold">= </span>getGrids2D<span style="font-weight: bold">(</span>pos2<span style="font-weight: bold">)
    </span>bestDistance <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>default
    <span style="color: blue; font-weight: bold">for </span>pos1Snap<span style="font-weight: bold">, </span>snap1Distance <span style="color: blue; font-weight: bold">in </span>pos1Grids<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">for </span>pos2Snap<span style="font-weight: bold">, </span>snap2Distance <span style="color: blue; font-weight: bold">in </span>pos2Grids<span style="font-weight: bold">:
        </span>gridDistance <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>getDistanceOnGrid<span style="font-weight: bold">(</span>pos1Snap<span style="font-weight: bold">, </span>pos2Snap<span style="font-weight: bold">)
        </span>distance <span style="font-weight: bold">= </span>gridDistance <span style="font-weight: bold">+ </span>snap1Distance <span style="font-weight: bold">+ </span>snap2Distance
        <span style="color: blue; font-weight: bold">if </span>bestDistance <span style="font-weight: bold">&gt; </span>distance<span style="font-weight: bold">:
          </span>bestDistance <span style="font-weight: bold">= </span>distance
    <span style="color: blue; font-weight: bold">return </span>bestDistance

  <span style="color: blue; font-weight: bold">def </span>getDistanceOnGrid<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>pos1<span style="font-weight: bold">, </span>pos2<span style="font-weight: bold">):
    </span>key <span style="font-weight: bold">= (</span>pos1<span style="font-weight: bold">, </span>pos2<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>key <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_distances<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_distances<span style="font-weight: bold">[</span>key<span style="font-weight: bold">]
    </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">raise </span>Exception<span style="font-weight: bold">(</span><span style="color: red">"Positions not in grid: " </span><span style="font-weight: bold">+ </span>str<span style="font-weight: bold">(</span>key<span style="font-weight: bold">))

  </span><span style="color: blue; font-weight: bold">def </span>isReadyForMazeDistance<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_distances <span style="font-weight: bold">!= </span><span style="color: blue">None

</span><span style="color: blue; font-weight: bold">def </span>manhattanDistance<span style="font-weight: bold">(</span>x<span style="font-weight: bold">, </span>y <span style="font-weight: bold">):
  </span><span style="color: blue; font-weight: bold">return </span>abs<span style="font-weight: bold">( </span>x<span style="font-weight: bold">[</span><span style="color: red">0</span><span style="font-weight: bold">] - </span>y<span style="font-weight: bold">[</span><span style="color: red">0</span><span style="font-weight: bold">] ) + </span>abs<span style="font-weight: bold">( </span>x<span style="font-weight: bold">[</span><span style="color: red">1</span><span style="font-weight: bold">] - </span>y<span style="font-weight: bold">[</span><span style="color: red">1</span><span style="font-weight: bold">] )

</span><span style="color: blue; font-weight: bold">def </span>isInt<span style="font-weight: bold">(</span>pos<span style="font-weight: bold">):
  </span>x<span style="font-weight: bold">, </span>y <span style="font-weight: bold">= </span>pos
  <span style="color: blue; font-weight: bold">return </span>x <span style="font-weight: bold">== </span>int<span style="font-weight: bold">(</span>x<span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span>y <span style="font-weight: bold">== </span>int<span style="font-weight: bold">(</span>y<span style="font-weight: bold">)

</span><span style="color: blue; font-weight: bold">def </span>getGrids2D<span style="font-weight: bold">(</span>pos<span style="font-weight: bold">):
  </span>grids <span style="font-weight: bold">= []
  </span><span style="color: blue; font-weight: bold">for </span>x<span style="font-weight: bold">, </span>xDistance <span style="color: blue; font-weight: bold">in </span>getGrids1D<span style="font-weight: bold">(</span>pos<span style="font-weight: bold">[</span><span style="color: red">0</span><span style="font-weight: bold">]):
    </span><span style="color: blue; font-weight: bold">for </span>y<span style="font-weight: bold">, </span>yDistance <span style="color: blue; font-weight: bold">in </span>getGrids1D<span style="font-weight: bold">(</span>pos<span style="font-weight: bold">[</span><span style="color: red">1</span><span style="font-weight: bold">]):
      </span>grids<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(((</span>x<span style="font-weight: bold">, </span>y<span style="font-weight: bold">), </span>xDistance <span style="font-weight: bold">+ </span>yDistance<span style="font-weight: bold">))
  </span><span style="color: blue; font-weight: bold">return </span>grids
  
<span style="color: blue; font-weight: bold">def </span>getGrids1D<span style="font-weight: bold">(</span>x<span style="font-weight: bold">):
  </span>intX <span style="font-weight: bold">= </span>int<span style="font-weight: bold">(</span>x<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">if </span>x <span style="font-weight: bold">== </span>int<span style="font-weight: bold">(</span>x<span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">[(</span>x<span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">)]
  </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">[(</span>intX<span style="font-weight: bold">, </span>x<span style="font-weight: bold">-</span>intX<span style="font-weight: bold">), (</span>intX<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">, </span>intX<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">-</span>x<span style="font-weight: bold">)]
  
</span><span style="color: green; font-style: italic">##########################################
# MACHINERY FOR COMPUTING MAZE DISTANCES #
##########################################

</span>distanceMap <span style="font-weight: bold">= {}
</span>distanceMapSemaphore <span style="font-weight: bold">= </span>threading<span style="font-weight: bold">.</span>Semaphore<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">)
</span>distanceThread <span style="font-weight: bold">= </span><span style="color: blue">None

</span><span style="color: blue; font-weight: bold">def </span>waitOnDistanceCalculator<span style="font-weight: bold">(</span>t<span style="font-weight: bold">):
  </span><span style="color: blue; font-weight: bold">global </span>distanceThread
  <span style="color: blue; font-weight: bold">if </span>distanceThread <span style="font-weight: bold">!= </span><span style="color: blue">None</span><span style="font-weight: bold">:
    </span>time<span style="font-weight: bold">.</span>sleep<span style="font-weight: bold">(</span>t<span style="font-weight: bold">)

</span><span style="color: blue; font-weight: bold">class </span>DistanceCalculator<span style="font-weight: bold">(</span>threading<span style="font-weight: bold">.</span>Thread<span style="font-weight: bold">):
  </span><span style="color: blue; font-weight: bold">def </span>setAttr<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>layout<span style="font-weight: bold">, </span>distancer<span style="font-weight: bold">, </span>default <span style="font-weight: bold">= </span><span style="color: red">10000</span><span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout <span style="font-weight: bold">= </span>layout
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>distancer <span style="font-weight: bold">= </span>distancer
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>default <span style="font-weight: bold">= </span>default
  
  <span style="color: blue; font-weight: bold">def </span>run<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">global </span>distanceMap<span style="font-weight: bold">, </span>distanceThread
    distanceMapSemaphore<span style="font-weight: bold">.</span>acquire<span style="font-weight: bold">()

    </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout<span style="font-weight: bold">.</span>walls <span style="color: blue; font-weight: bold">not in </span>distanceMap<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">if </span>distanceThread <span style="font-weight: bold">!= </span><span style="color: blue">None</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">raise </span>Exception<span style="font-weight: bold">(</span><span style="color: red">'Multiple distance threads'</span><span style="font-weight: bold">)
      </span>distanceThread <span style="font-weight: bold">= </span><span style="color: blue">self

      </span>distances <span style="font-weight: bold">= </span>computeDistances<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout<span style="font-weight: bold">)
      </span><span style="color: blue; font-weight: bold">print </span><span style="font-weight: bold">&gt;&gt;</span>sys<span style="font-weight: bold">.</span>stdout<span style="font-weight: bold">, </span><span style="color: red">'[Distancer]: Switching to maze distances' 

      </span>distanceMap<span style="font-weight: bold">[</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout<span style="font-weight: bold">.</span>walls<span style="font-weight: bold">] = </span>distances
      distanceThread <span style="font-weight: bold">= </span><span style="color: blue">None
    </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
      </span>distances <span style="font-weight: bold">= </span>distanceMap<span style="font-weight: bold">[</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout<span style="font-weight: bold">.</span>walls<span style="font-weight: bold">]

    </span>distanceMapSemaphore<span style="font-weight: bold">.</span>release<span style="font-weight: bold">()
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>distancer<span style="font-weight: bold">.</span>_distances <span style="font-weight: bold">= </span>distances  

<span style="color: blue; font-weight: bold">def </span>computeDistances<span style="font-weight: bold">(</span>layout<span style="font-weight: bold">):
    </span>distances <span style="font-weight: bold">= {}
    </span>allNodes <span style="font-weight: bold">= </span>layout<span style="font-weight: bold">.</span>walls<span style="font-weight: bold">.</span>asList<span style="font-weight: bold">(</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">for </span>source <span style="color: blue; font-weight: bold">in </span>allNodes<span style="font-weight: bold">:
        </span>dist <span style="font-weight: bold">= {}
        </span>closed <span style="font-weight: bold">= {}
        </span><span style="color: blue; font-weight: bold">for </span>node <span style="color: blue; font-weight: bold">in </span>allNodes<span style="font-weight: bold">:
            </span>dist<span style="font-weight: bold">[</span>node<span style="font-weight: bold">] = </span>sys<span style="font-weight: bold">.</span>maxint
        <span style="color: blue; font-weight: bold">import </span>util
        queue <span style="font-weight: bold">= </span>util<span style="font-weight: bold">.</span>PriorityQueue<span style="font-weight: bold">()
        </span>queue<span style="font-weight: bold">.</span>push<span style="font-weight: bold">(</span>source<span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">)
        </span>dist<span style="font-weight: bold">[</span>source<span style="font-weight: bold">] = </span><span style="color: red">0
        </span><span style="color: blue; font-weight: bold">while not </span>queue<span style="font-weight: bold">.</span>isEmpty<span style="font-weight: bold">():
            </span>node <span style="font-weight: bold">= </span>queue<span style="font-weight: bold">.</span>pop<span style="font-weight: bold">()
            </span><span style="color: blue; font-weight: bold">if </span>node <span style="color: blue; font-weight: bold">in </span>closed<span style="font-weight: bold">:
                </span><span style="color: blue; font-weight: bold">continue
            </span>closed<span style="font-weight: bold">[</span>node<span style="font-weight: bold">] = </span><span style="color: blue; font-weight: bold">True
            </span>nodeDist <span style="font-weight: bold">= </span>dist<span style="font-weight: bold">[</span>node<span style="font-weight: bold">]
            </span>adjacent <span style="font-weight: bold">= []
            </span>x<span style="font-weight: bold">, </span>y <span style="font-weight: bold">= </span>node
            <span style="color: blue; font-weight: bold">if not </span>layout<span style="font-weight: bold">.</span>isWall<span style="font-weight: bold">((</span>x<span style="font-weight: bold">,</span>y<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">)):
                </span>adjacent<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>x<span style="font-weight: bold">,</span>y<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">))
            </span><span style="color: blue; font-weight: bold">if not </span>layout<span style="font-weight: bold">.</span>isWall<span style="font-weight: bold">((</span>x<span style="font-weight: bold">,</span>y<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">)):
                </span>adjacent<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>x<span style="font-weight: bold">,</span>y<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">) )
            </span><span style="color: blue; font-weight: bold">if not </span>layout<span style="font-weight: bold">.</span>isWall<span style="font-weight: bold">((</span>x<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">,</span>y<span style="font-weight: bold">)):
                </span>adjacent<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>x<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">,</span>y<span style="font-weight: bold">) )
            </span><span style="color: blue; font-weight: bold">if not </span>layout<span style="font-weight: bold">.</span>isWall<span style="font-weight: bold">((</span>x<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">,</span>y<span style="font-weight: bold">)):
                </span>adjacent<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>x<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">,</span>y<span style="font-weight: bold">))
            </span><span style="color: blue; font-weight: bold">for </span>other <span style="color: blue; font-weight: bold">in </span>adjacent<span style="font-weight: bold">:
                </span><span style="color: blue; font-weight: bold">if not </span>other <span style="color: blue; font-weight: bold">in </span>dist<span style="font-weight: bold">:
                    </span><span style="color: blue; font-weight: bold">continue
                </span>oldDist <span style="font-weight: bold">= </span>dist<span style="font-weight: bold">[</span>other<span style="font-weight: bold">]
                </span>newDist <span style="font-weight: bold">= </span>nodeDist<span style="font-weight: bold">+</span><span style="color: red">1
                </span><span style="color: blue; font-weight: bold">if </span>newDist <span style="font-weight: bold">&lt; </span>oldDist<span style="font-weight: bold">:
                    </span>dist<span style="font-weight: bold">[</span>other<span style="font-weight: bold">] = </span>newDist
                    queue<span style="font-weight: bold">.</span>push<span style="font-weight: bold">(</span>other<span style="font-weight: bold">, </span>newDist<span style="font-weight: bold">)
        </span><span style="color: blue; font-weight: bold">for </span>target <span style="color: blue; font-weight: bold">in </span>allNodes<span style="font-weight: bold">:
            </span>distances<span style="font-weight: bold">[(</span>target<span style="font-weight: bold">, </span>source<span style="font-weight: bold">)] = </span>dist<span style="font-weight: bold">[</span>target<span style="font-weight: bold">]
    </span><span style="color: blue; font-weight: bold">return </span>distances
    

<span style="color: blue; font-weight: bold">def </span>getDistanceOnGrid<span style="font-weight: bold">(</span>distances<span style="font-weight: bold">, </span>pos1<span style="font-weight: bold">, </span>pos2<span style="font-weight: bold">):
    </span>key <span style="font-weight: bold">= (</span>pos1<span style="font-weight: bold">, </span>pos2<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>key <span style="color: blue; font-weight: bold">in </span>distances<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>distances<span style="font-weight: bold">[</span>key<span style="font-weight: bold">]
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">100000
  
</span>
  </pre>
  </body>
  </html>
  